package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 226.翻转二叉树
 * 翻转一棵二叉树。
 *
 * @author Liyc
 * @date 2023/12/28 14:52
 **/

public class Solution5 {
    /**
     * 递归遍历翻转
     * 前后序遍历都可以
     * 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        swapChildren(root);//中
        invertTree(root.left);//左
        invertTree(root.right);//右
        return root;
    }

    /**
     * 迭代遍历翻转-用的层
     * @param root
     * @return
     */
    public TreeNode invertTree2(TreeNode root) {
        if(root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                swapChildren(node);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return root;
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}
